package com.yun.algorithmproblem.leetcode;

import java.util.LinkedList;
import java.util.Queue;

public class Leetcode752 {
    public int openLock(String[] deadends, String target) {
        int[][][][][] dist = new int[10][10][10][10][1];
        Queue<int[]> queue = new LinkedList<>();
        char[] targetCh = target.toCharArray();
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                for (int k = 0; k < 10; k++) {
                    for (int l = 0; l < 10; l++) {
                        dist[i][j][k][l][0] = Integer.MAX_VALUE;
                    }
                }
            }
        }
        for (String deadend : deadends) {
            char[] chars = deadend.toCharArray();
            dist[chars[0]-'0'][chars[1]-'0'][chars[2]-'0'][chars[3]-'0'][0] = -1;
        }
        if(dist[0][0][0][0][0]==-1){
            return -1;
        }
        dist[0][0][0][0][0] = 0;
        queue.offer(new int[]{0, 0, 0, 0});
        int[] d1 = new int[]{-1, 1, 0, 0, 0, 0, 0, 0};
        int[] d2 = new int[]{0, 0, -1, 1, 0, 0, 0, 0};
        int[] d3 = new int[]{0, 0, 0, 0, -1, 1, 0, 0};
        int[] d4 = new int[]{0, 0, 0, 0, 0, 0, -1, 1};
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int num1 = curr[0], num2 = curr[1], num3 = curr[2], num4 = curr[3];
            for (int i = 0; i < 8; i++) {
                int newNum1 = move(num1, d1[i]);
                int newNum2 = move(num2, d2[i]);
                int newNum3 = move(num3, d3[i]);
                int newNum4 = move(num4, d4[i]);
                if (dist[newNum1][newNum2][newNum3][newNum4][0] <= dist[num1][num2][num3][num4][0] + 1) {
                    continue;
                }
                dist[newNum1][newNum2][newNum3][newNum4][0] = dist[num1][num2][num3][num4][0] + 1;
                queue.offer(new int[]{newNum1, newNum2, newNum3, newNum4});
            }
        }
        int res = dist[targetCh[0]-'0'][targetCh[1]-'0'][targetCh[2]-'0'][targetCh[3]-'0'][0];
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    private int move(int i, int j) {
        int sum = i + j;
        if (sum < 0) {
            sum = 9;
        } else if (sum > 9) {
            sum = 0;
        }
        return sum;
    }
}
